QuickLexSort: An efficient algorithm for lexicographically sorting nested restrictions of a database

摘要

Lexicographical sorting is a fundamental problem with applications tocontingency tables, databases, Bayesian networks, and more. A standard methodto lexicographically sort general data is to iteratively use a stable sort -- asort which preserves existing orders. Here we present a new method oflexicographical sorting called QuickLexSort. Whereas a stable sort basedlexicographical sorting algorithm operates from the least important to mostimportant features, in contrast, QuickLexSort sorts from the most important toleast important features, refining the sort as it goes. QuickLexSort firstrequires a one-time modest pre-processing step where each feature of the dataset is sorted independently. When lexicographically sorting a database,QuickLexSort (including pre-processing) has comparable running time to using astable sort based approach. For a data base with $m$ rows and $n$ columns, anda sorting algorithm running in time $O(mlog(m))$, a stable sort basedlexicographical sort and QuickLexSort will both take time $O(nmlog(m))$.However in many applications one has the need to lexicographically sort nesteddata, e.g.\ all possible sub-matrices up to a certain cardinality of columns.In such cases we show QuickLexSort gives a performance improvement of a logfactor of the database length (rows in matrix) over using a standard stablesort based approach. E.g.\ to sort all sub-matrices up to cardinality $k$,QuickLexSort has running time $O(mn^k)$ whereas a stable sort basedlexicographical sort will take time $O(mlog(m)n^k)$. After the pre-processingstep that is run only once for the entire matrix, QuickLexSort has a runningtime linear in the number of nested sub-matrices to sort. We conclude with anapplication to Bayesian network scoring to detect epistasis using SNP markerdata.